{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\" style=\"text-align:right\"><i>Peter Norvig<br>May 2015</i></div>\n",
    "\n",
    "# When Cheryl Met Eve: A Birthday Story\n",
    "\n",
    "The *Cheryl's Birthday* logic puzzle  [made the rounds](https://www.google.com/webhp?#q=cheryl%27s+birthday),\n",
    "and  I wrote [code](Cheryl.ipynb) that solves it. In that notebook I said that one reason for solving the problem with code rather than pencil and paper is that you can do more with code.  \n",
    "\n",
    "**[Gabe Gaster](http://www.gabegaster.com/)** proved me right when he [tweeted](https://twitter.com/gabegaster/status/593976413314777089/photo/1)  that he had extended my code to generate a new list of dates that satisfies the constraints of the puzzle:\n",
    "\n",
    "     January 15, January 4,\n",
    "     July 13, July 24, July 30,\n",
    "     March 13, March 24,\n",
    "     May 11, May 17, May 30\n",
    "\n",
    "In this notebook, I verify Gabe's result, and find some other variations on the puzzle.\n",
    "\n",
    "First, let's recap  [the puzzle](https://en.wikipedia.org/wiki/Cheryl%27s_Birthday):\n",
    "\n",
    "> 1. Albert and Bernard became friends with Cheryl, and want to know when her birthday is. Cheryl gave them a list of 10 possible dates:\n",
    "           May 15     May 16     May 19\n",
    "          June 17    June 18\n",
    "          July 14    July 16\n",
    "        August 14  August 15  August 17\n",
    "> 2. **Cheryl** then privately tells Albert the month and Bernard the day of her birthday.\n",
    "> 3. **Albert**: \"I don't know when Cheryl's birthday is, and I know that Bernard does not know.\"\n",
    "> 4. **Bernard**: \"At first I don't know when Cheryl's birthday is, but I know now.\"\n",
    "> 5. **Albert**: \"Then I also know when Cheryl's birthday is.\"\n",
    "> 6. So when is Cheryl's birthday?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Code for Original Cheryl's Birthday Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a slight modification of my [previous code](Cheryl.ipynb), and I'll give a slight modification of the explanation. The puzzle concerns these concepts:\n",
    "\n",
    "- **Possible dates** that might be Cheryl's birthday.\n",
    "- **Knowing** which dates are still possible; knowing for sure when only one is possible.\n",
    "- **Telling** Albert and Bernard specific facts about the birthday.\n",
    "- **Statements** about knowledge.\n",
    "- **Hearing** the statements about knowledge.\n",
    "\n",
    "I implement them as follows:\n",
    "- `dates` is a set of all possible dates (each date is a string); we also consider subsets of `dates`.\n",
    "- `know(possible_dates)` is a function that returns `True` when there is only one possible date.\n",
    "- `told(part)` is a function that returns the set of possible dates after Cheryl tells a part (month or day).\n",
    "- *`statement`*`(date)` returns true if the statement is true given that `date` is Cheryl's birthday.\n",
    "- `satisfy(possible_dates, statement,...)` returns a subset of possible_dates that are still possible after hearing the statements.\n",
    "\n",
    "In the [previous code](Cheryl.ipynb) I treated `dates` as a constant, but in this version the whole point is exploring different possible sets of dates, so now `dates` is a global variable, and the function `set_dates` is used to set the value of the global variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. \n",
    "# Cheryl gave them a list of 10 possible dates:\n",
    "\n",
    "dates = ['May 15',    'May 16',    'May 19',\n",
    "        'June 17',   'June 18',\n",
    "        'July 14',   'July 16',\n",
    "      'August 14', 'August 15', 'August 17']\n",
    "\n",
    "def month(date): return date.split()[0]\n",
    "\n",
    "def day(date):   return date.split()[1]\n",
    "\n",
    "# Cheryl then tells Albert and Bernard separately \n",
    "# the month and the day of the birthday respectively.\n",
    "\n",
    "BeliefState = set\n",
    "\n",
    "def told(part: str) -> BeliefState:\n",
    "    \"\"\"Cheryl told a part of her birthdate to someone; return a belief state of possible dates.\"\"\"\n",
    "    return {date for date in dates if part in date}\n",
    "\n",
    "def know(beliefs: BeliefState) -> bool:\n",
    "    \"\"\"A person `knows` the answer if their belief state has only one possibility.\"\"\"\n",
    "    return len(beliefs) == 1\n",
    "\n",
    "def satisfy(some_dates, *statements) -> BeliefState:\n",
    "    \"\"\"Return the subset of dates that satisfy all the statements.\"\"\"\n",
    "    return {date for date in some_dates\n",
    "            if all(statement(date) for statement in statements)}\n",
    "\n",
    "# Albert and Bernard make three statements:\n",
    "\n",
    "def albert1(date) -> bool:\n",
    "    \"\"\"Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.\"\"\"\n",
    "    albert_beliefs = told(month(date))\n",
    "    return not know(albert_beliefs) and not satisfy(albert_beliefs, bernard_knows)\n",
    "\n",
    "def bernard_knows(date) -> bool: return know(told(day(date))) \n",
    "\n",
    "def bernard1(date) -> bool:\n",
    "    \"\"\"Bernard: At first I don't know when Cheryl's birthday is, but I know now.\"\"\"\n",
    "    at_first_beliefs = told(day(date))\n",
    "    after_beliefs   = satisfy(at_first_beliefs, albert1)\n",
    "    return not know(at_first_beliefs) and know(after_beliefs)\n",
    "\n",
    "def albert2(date) -> bool:\n",
    "    \"\"\"Albert: Then I also know when Cheryl's birthday is.\"\"\"\n",
    "    then = satisfy(told(month(date)), bernard1)\n",
    "    return know(then)\n",
    "    \n",
    "# So when is Cheryl's birthday?\n",
    "\n",
    "def cheryls_birthday(dates) -> BeliefState:\n",
    "    \"\"\"Return a subset of the global `dates` for which all three statements are true.\"\"\"\n",
    "    return satisfy(set_dates(dates), albert1, bernard1, albert2)\n",
    "\n",
    "def set_dates(new_dates):\n",
    "    \"\"\"Set the value of the global `dates` to `new_dates`\"\"\"\n",
    "    global dates\n",
    "    dates = new_dates\n",
    "    return dates\n",
    "\n",
    "# Some tests\n",
    "\n",
    "assert month('May 19') == 'May'\n",
    "assert day('May 19') == '19'\n",
    "assert albert1('May 19') == False\n",
    "assert albert1('July 14') == True\n",
    "assert know(told('17')) == False\n",
    "assert know(told('19')) == True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 16'}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cheryls_birthday(dates)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'August 14', 'August 15', 'August 17', 'July 14', 'July 16'}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(dates, albert1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'August 15', 'August 17', 'July 16'}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(dates, albert1, bernard1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 16'}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(dates, albert1, bernard1, albert2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Verifying Gabe's Version"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gabe tweeted these ten dates:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "gabe_dates = [\n",
    "  'January 15', 'January 4',\n",
    "  'July 13',    'July 24',   'July 30',\n",
    "  'March 13',   'March 24',\n",
    "  'May 11',     'May 17',    'May 30']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can verify that they do indeed make the puzzle work, giving a single known birthdate:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 30'}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cheryls_birthday(gabe_dates)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Creating Our Own Versions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If Gabe can do it, we can do it!  Our strategy will be to repeatedly pick a random sample of dates, and check if they solve the puzzle. We'll limit ourselves to a subset of dates (not all 366) to make it more likely that a random selection will have multiple dates with the same month and day (otherwise Albert and Bernard would know right away):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "many_dates = {mo + ' ' + d1 + d2\n",
    "              for mo in ('March', 'April', 'May', 'June', 'July')\n",
    "              for d1 in '12'\n",
    "              for d2 in '3456789'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need to cycle through random samples of these possible dates until we hit one that works.  I anticipate wanting to solve other puzzles besides the original `cheryls_birthday`, so I'll make the `puzzle` be a parameter of the function `pick_dates`. Note that `pick_dates` returns two things: the one date that is the solution (the birthday), and the `k` (default 10) dates that form the puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def pick_dates(puzzle=cheryls_birthday, k=10):\n",
    "    \"Pick a set of `k` dates for which the `puzzle` has a unique solution.\"\n",
    "    while True:\n",
    "        random_dates = random.sample(many_dates, k)\n",
    "        solutions = puzzle(random_dates)\n",
    "        if know(solutions):\n",
    "            return solutions.pop(), random_dates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('May 27',\n",
       " ['May 13',\n",
       "  'April 23',\n",
       "  'May 27',\n",
       "  'April 18',\n",
       "  'July 14',\n",
       "  'May 23',\n",
       "  'July 27',\n",
       "  'March 18',\n",
       "  'June 19',\n",
       "  'March 13'])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pick_dates()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('July 24',\n",
       " ['July 25', 'July 24', 'March 25', 'July 28', 'April 24', 'March 28'])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pick_dates(k=6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('May 25',\n",
       " ['July 28',\n",
       "  'March 19',\n",
       "  'July 29',\n",
       "  'July 13',\n",
       "  'April 27',\n",
       "  'June 27',\n",
       "  'May 25',\n",
       "  'April 28',\n",
       "  'April 18',\n",
       "  'July 25',\n",
       "  'June 15',\n",
       "  'May 18'])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pick_dates(k=12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! We can make a new puzzle, just like Gabe.  But how often do we get a unique solution to the puzzle (that is, the puzzle returns a set of size 1)?  How often do we get a solution where Albert and Bernard know, but we the puzzle solver doesn't (that is, a set of size greater than 1)?  How often is there no solution (size 0)? Let's make a Counter of the number of times each length-of-solution occurs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def solution_lengths(puzzle=cheryls_birthday, N=10000, k=10, many_dates=many_dates):\n",
    "    \"Try N random samples and count how often each possible length-of-puzzle-solution appears.\"\n",
    "    return Counter(len(puzzle(random.sample(many_dates, k)))\n",
    "                   for _ in range(N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({0: 9513, 1: 210, 2: 276, 3: 1})"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution_lengths(cheryls_birthday)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This says that about 2% of the time we get a unique solution (a set of `len` 1). With similar frequency we get an ambiguous solution (with 2 or more possible birth dates).  And about 95% of the time, the sample of dates leads to no solution dates.\n",
    "\n",
    "What happens if Cheryl changes the number of possible dates?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({0: 9971, 2: 18, 1: 11})"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution_lengths(cheryls_birthday, k=6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({0: 9020, 2: 467, 1: 503, 3: 10})"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution_lengths(cheryls_birthday, k=12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is really hard (but not impossible) to find a set of 6 dates that work for the puzzle, and much easier to find a solution with 12 dates."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A New Puzzle: All About Eve"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's see if we can create a more complicated puzzle. We'll introduce a new character, Eve, give her a statement, and alter the rest of the puzzle slightly:\n",
    "\n",
    "> 1. Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl wrote down a list of 10 possible dates for all to see.\n",
    "> 2. **Cheryl** then writes down the month and shows it just to Albert, and also writes down the day and shows it just to Bernard.\n",
    "> 3. **Albert**: I don't know when Cheryl's birthday is, but I know that Bernard does not know either.\n",
    "> 4. **Bernard**: At first I didn't know when Cheryl's birthday is, but I know now.\n",
    "> 5. **Albert**: Then I also know when Cheryl's birthday is.\n",
    "> 6. **Eve**: Hi, Everybody. My name is Eve and I'm an evesdropper. It's what I do! I peeked and saw the first letter of the month and the first digit of the day. When I peeked, I didn't know Cheryl's birthday, but after listening to Albert and Bernard I do.  And it's a good thing I peeked, because otherwise I couldn't have\n",
    "figured it out.\n",
    "> 7. So when is Cheryl's birthday?\n",
    "\n",
    "We can easily code this up:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cheryls_birthday_with_eve(dates):\n",
    "    \"Return a set of the dates for which Albert, Bernard, and Eve's statements are true.\"\n",
    "    return satisfy(set_dates(dates), albert1, bernard1, albert2, eve1)\n",
    "\n",
    "def eve1(date):\n",
    "    \"\"\"Eve: I peeked and saw the first letter of the month and the first digit of the day. \n",
    "    When I peeked, I didn't know Cheryl's birthday, but after listening to Albert and Bernard \n",
    "    I do. And it's a good thing I peeked, because otherwise I couldn't have figured it out.\"\"\"\n",
    "    at_first = told(first(day(date))) & told(first(month(date)))\n",
    "    otherwise = told('')\n",
    "    return (not know(at_first) and\n",
    "                know(satisfy(at_first,  albert1, bernard1, albert2)) and\n",
    "            not know(satisfy(otherwise, albert1, bernard1, albert2)))\n",
    "\n",
    "def first(seq): return seq[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Note*: I admit I \"cheated\" a bit here.  Remember that the function `told`  tests for `(part in date)`.  For that to work for Eve, we have to make sure that the first letter is distinct from any other character in the date (it is&mdash;because only the first letter is uppercase) and that the first digit is distinct from any other character (it is&mdash;because in `many_dates` I carefully made sure that the first digit is always 1 or 2, and the second digit is never 1 or 2). Also note that `told('')` denotes the hypothetical situation where Cheryl \"told\" Eve nothing.\n",
    "\n",
    "I have no idea if it is possible to find a set of dates that works for this puzzle. But I can try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('March 18',\n",
       " ['April 25',\n",
       "  'March 18',\n",
       "  'March 16',\n",
       "  'April 27',\n",
       "  'May 29',\n",
       "  'July 28',\n",
       "  'May 24',\n",
       "  'July 16',\n",
       "  'May 28',\n",
       "  'April 18'])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pick_dates(puzzle=cheryls_birthday_with_eve)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was easy.  How often is a random sample of dates a solution to this puzzle?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({0: 9729, 1: 143, 2: 128})"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution_lengths(cheryls_birthday_with_eve)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "About half as often as for the original puzzle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# An Even More Complex Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's make the puzzle even more complicated by making Albert wait one more time before he finally knows:\n",
    "\n",
    "> 1. Albert and Bernard just became friends with Cheryl, and they want to know when her birtxhday is. Cheryl wrote down a list of 10 possible dates for all to see.\n",
    "> 2. **Cheryl** then writes down the month and shows it just to Albert, and also writes down the day and shows it just to Bernard.\n",
    "> 3. **Albert**: I don't know when Cheryl's birthday is, but I know that Bernard does not know either. \n",
    "> 4. **Bernard**: At first I didn't know when Cheryl's birthday is, but I know now.\n",
    "> 5. **Albert**: I still don't know.\n",
    "> 6. **Eve**: Hi, Everybody. My name is Eve and I'm an evesdropper. It's what I do! I peeked and saw the first letter of the month and the first digit of the day. When I peeked, I didn't know Cheryl's birthday, but after listening to Albert and Bernard I do.  And it's a good thing I peeked, because otherwise I couldn't have\n",
    "figured it out.\n",
    "> 7. **Albert**: OK, now I know.\n",
    "> 8. So when is Cheryl's birthday?\n",
    "\n",
    "Let's be careful in coding this up; Albert's second statement is different; he has a new third statement; and Eve's statement uses the same words, but it now implicitly refers to a different statement by Albert. We'll use the names `albert2c`,  `eve1c`, and `albert3c` (`c` for \"complex\") to represent the new statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cheryls_birthday_complex(dates):\n",
    "    \"Return a set of the dates for which Albert, Bernard, and Eve's statements are true.\"\n",
    "    return satisfy(set_dates(dates), albert1, bernard1, albert2c, eve1c, albert3c)\n",
    "\n",
    "def albert2c(date):\n",
    "    \"Albert: I still don't know.\"\n",
    "    return not know(satisfy(told(month(date)), bernard1))\n",
    "\n",
    "def eve1c(date):\n",
    "    \"\"\"Eve: I peeked and saw the first letter of the month and the first digit of the day. \n",
    "    When I peeked, I didn't know Cheryl's birthday, but after listening to Albert and Bernard \n",
    "    I do. And it's a good thing I peeked, because otherwise I couldn't have figured it out.\"\"\"\n",
    "    at_first = told(first(day(date))) & told(first(month(date)))\n",
    "    otherwise = told('')\n",
    "    return (not know(at_first)\n",
    "            and know(satisfy(at_first, albert1, bernard1, albert2c)) and\n",
    "            not know(satisfy(otherwise, albert1, bernard1, albert2c)))\n",
    "\n",
    "def albert3c(date):\n",
    "    \"Albert: OK, now I know.\"\n",
    "    return know(satisfy(told(month(date)), bernard1, eve1c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, I don't know if it is possible to find dates that works with this story, but I can try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('March 29',\n",
       " ['June 16',\n",
       "  'March 13',\n",
       "  'March 29',\n",
       "  'May 25',\n",
       "  'June 13',\n",
       "  'April 23',\n",
       "  'April 14',\n",
       "  'June 29',\n",
       "  'March 14',\n",
       "  'June 27'])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pick_dates(puzzle=cheryls_birthday_complex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It worked!  Were we just lucky, or are there many sets of dates that work?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({0: 9408, 1: 591, 2: 1})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution_lengths(cheryls_birthday_complex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interesting. It was actually easier to find dates that work for this story than for either of the other stories."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analyzing a Solution to the Complex Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will go through a solution step-by-step.  We'll use a set of dates selected in a previous run:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "previous_run_dates = {\n",
    "  'April 28',\n",
    "  'July 27',\n",
    "  'June 19',\n",
    "  'June 16',\n",
    "  'July 15',\n",
    "  'April 15',\n",
    "  'June 29',\n",
    "  'July 16',\n",
    "  'May 24',\n",
    "  'May 27'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's find the solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 27'}"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cheryls_birthday_complex(previous_run_dates)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the first step is that Albert was told \"July\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 15', 'July 16', 'July 27'}"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "told('July')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And no matter which of these three dates is the actual birthday, Albert knows that Bernard would not know the birthday, because each of the days (15, 16, 27) appears twice in the list of possible dates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "not know(told('15')) and not know(told('16')) and not know(told('27'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, Bernard is told the day:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 27', 'May 27'}"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "told('27')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are two dates with a 27, so Bernard did not know then. But only one of these dates is still consistent after hearing Albert's statement:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 27'}"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(told('27'), albert1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So after Albert's statement, Bernard knows. Poor Albert still doesn't know (after being told `'July'` and hearing Bernard's statement):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 15', 'July 16', 'July 27'}"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(told('July'), bernard1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then along comes Eve. She evesdrops the \"J\" and the \"2\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 27', 'June 29'}"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "told('J') & told('2')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Two dates, so Eve doesn't know yet. But only one of the dates works after hearing the three statements made by Albert and Bernard:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 27'}"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(told('J') & told('2'), albert1, bernard1, albert2c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But Eve wouldn't have known if she had been told nothing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 15', 'July 16', 'July 27'}"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(told(''), albert1, bernard1, albert2c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What about Albert?  After hearing Eve's statement he finally knows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 27'}"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(told('July'), eve1c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Three Children\n",
    "\n",
    "Here's another puzzle:\n",
    "\n",
    "> 1. A parent has the following conversation with a friend:\n",
    "> 2. **Parent:** the product of my three childrens' ages is 36.\n",
    "> 3. **Friend**: I don't know their ages.\n",
    "> 4. **Parent**: The sum of their ages is the same as the number of people in this room.\n",
    "> 5. **Friend**: I still don't know their ages.\n",
    "> 6. **Parent**: The oldest one likes bananas.\n",
    "> 7. **Friend**: Now I know their ages.\n",
    "\n",
    "Let's follow the same methodology to solve this puzzle. Except this time, we're not dealing with sets of possible dates, we're dealing with set of possible *states* of the world. We'll define a state as a tuple of 4 numbers: the ages of the three children (in increasing order), and the number of people in the room. \n",
    "\n",
    "Note: We'll limit the children's ages to be below 30 and the number of people in the room to be below 90. Also, in `friend2` and `friend3` we'll compute the `possible_states` and cache them, since the computation does not depend on the `date`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(2, 2, 9, 13)}"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N      = 30\n",
    "states = {(a, b, c, n) \n",
    "          for a in range(1, N)\n",
    "          for b in range(a, N)\n",
    "          for c in range(b, N) if a * b * c == 36\n",
    "          for n in range(2, 90)}\n",
    "\n",
    "def ages(state): return state[:-1]\n",
    "def room(state): return state[-1]\n",
    "\n",
    "def parent1(state): \n",
    "    \"\"\"The product of my three childrens' ages is 36.\"\"\"\n",
    "    a, b, c = ages(state)\n",
    "    return a * b * c == 36\n",
    "\n",
    "def friend1(state): \n",
    "    \"\"\"I don't know their ages.\"\"\"\n",
    "    possible_ages = {ages(s) for s in satisfy(states, parent1)}\n",
    "    return not know(possible_ages)\n",
    "\n",
    "def parent2(state):\n",
    "    \"\"\"The sum of their ages is the same as the number of people in this room.\"\"\"\n",
    "    return sum(ages(state)) == room(state)\n",
    "\n",
    "def friend2(state, possible_states=satisfy(states, parent1, friend1, parent2)): \n",
    "    \"\"\"I still don't know their ages.\"\"\"\n",
    "    # Given there are room(state) people in the room, I still don't know the ages.\n",
    "    possible_ages = {ages(s) for s in possible_states if room(s) == room(state)}\n",
    "    return not know(possible_ages)\n",
    "\n",
    "def parent3(state):\n",
    "    \"\"\"The oldest one likes bananas.\"\"\"\n",
    "    # I.e., there is an oldest one (and not twins of the same age)\n",
    "    a, b, c = ages(state)\n",
    "    return c > b\n",
    "\n",
    "def friend3(state, possible_states=satisfy(states, parent1, friend1, parent2, friend2, parent3)): \n",
    "    \"Now I know their ages.\"\n",
    "    possible_ages = {ages(s) for s in possible_states}\n",
    "    return know(possible_ages)\n",
    "\n",
    "def child_age_puzzle(states):\n",
    "    return satisfy(states, parent1, friend1, parent2, friend2, parent3, friend3)\n",
    "\n",
    "child_age_puzzle(states)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The tricky part of this puzzle comes after the `parent2` statement:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(1, 2, 18, 21),\n",
       " (1, 3, 12, 16),\n",
       " (1, 4, 9, 14),\n",
       " (1, 6, 6, 13),\n",
       " (2, 2, 9, 13),\n",
       " (2, 3, 6, 11),\n",
       " (3, 3, 4, 10)}"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(states, parent1, friend1, parent2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that out of these 7 possibilities, if the number of people in the room (the last number in each tuple) \n",
    "were anything other than 13, then the friend (who can observe the number of people in the room) would know the ages. Since the `friend2` statement professes continued ignorance, it must be that the number of people in the room is 13. Then the `parent3` statement makes it clear that there can't be 6-year-old twins as the oldest children; it must be 2-year-old twins with an oldest age 9."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What Next?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you like, there are many other directions you could take this:\n",
    "\n",
    "- Could you create a puzzle that goes one or two rounds more before everyone knows?\n",
    "- Could you add new characters: Faith, and then George, and maybe even a new Hope?\n",
    "- Would it be more interesting with a different number of possible dates (not 10)?\n",
    "- Should we include the year or the day of the week, as well as the month and day?\n",
    "- Perhaps a puzzle that starts with [Richard Smullyan](http://en.wikipedia.org/wiki/Raymond_Smullyan) announcing that one of the characters is a liar.\n",
    "- Or you could make a puzzle harder than [the hardest logic puzzle ever](https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever).\n",
    "- Try the \"black and white hats\" [Riddler Express](https://fivethirtyeight.com/features/can-you-solve-these-colorful-puzzles/) stumper.\n",
    "- It's up to you ..."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
